Reliable data transmission over a communication channel is fundamental in all fields of information and communication technology. Unfortunately, most communication channels in the real world are noisy, so that the signal is distorted on its way from the sender to the receiver. Signal distortions can be due both to imperfections of the sender and/or receiver equipment, or to external influences during transmission. Error-correcting codes have been developed to identify and correct such errors, so that, after correction, the recipient receives a (nearly) exact copy of the data transmitted by the sender with a high level of certainty. Typically, the particular code is chosen based on some information about the infidelities of the channel through which the data is transmitted, as well as the nature of the data.
A class of error-correcting codes with high practical relevance are Reed-Solomon error-correcting codes, which protect messages by constructing a polynomial from the raw data. The polynomial is evaluated at several points, and these values are sent or recorded. Sampling the polynomial more often than necessary makes the polynomial over-determined, and as long as the recipient receives sufficiently many of these points correctly, she or he can recover the original polynomial even in the presence of transmission errors. Reed-Solomon codes are used in a wide variety of commercial applications, both for data storage on CDs, DVDs and blue ray discs as well as in broadcast systems such as digital television. They are particularly efficient to protect against burst errors, in which a whole train of subsequent data symbols is corrupted.
Reed-Solomon error-correcting codes can be encoded as “systematic codes”, i.e., the codeword contains the input data in its original form plus some parity symbols. The values of the parity symbols allow the decoder to determine whether the data has been lost or corrupted during transmission, and to correct for transmission errors. In conventional systematic Reed-Solomon encoding schemes, a block of parity symbols is simply appended or pre-appended to the un-altered block of (raw) data symbols.
In contrast, the upcoming ATSC mobile/handheld digital television standard (ATSC-M/H) is based on a Reed-Solomon code in which the parity symbols are no longer arranged in a block of consecutive symbols, but may be spread arbitrarily within the codeword. Section 5.4.9 and Table A.1 of the specification “ATSC-M/H Standard, Part 2, RF/Transmission System Characteristics (A/153, Part 2: 2009)”, published by the Advanced Television Systems Committee, suggest a systematic t=10 error-correcting Reed-Solomon code of length n=207 and dimension k=n−2×t=187 defined over the finite field IF256. The 2×t=20 parity symbols are supposed to be inserted according to one out of 118 different parity patterns, which specify the positions of the parity symbols in the codeword. These parity positions may differ from codeword to codeword. Conventional encoding circuits are adapted to codewords in which the parity symbols are arranged blockwise at fixed positions, and hence cannot be used to provide codewords with arbitrary parity positions.